package leetcode.editor.cn;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : P72
 * 功能概要  :
 *
 * @Author : yangwk
 * @Date : 2024/1/30 21:56
 */
public class P72 {
    public static void main(String[] args) {
        System.out.println(minDistance("horse","ros"));
    }

    public static int minDistance(String word1, String word2) {
        int word1len = word1.length();
        int word2len = word2.length();
        int[][] dp = new int[word1len+1][word2len+1];
        for (int i = 0; i <=word1len; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <=word2len; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= word1len; i++) {
            for (int j = 1; j <= word2len; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                }
            }
        }
        return dp[word1len][word2len];
    }
}
